//
// Description: 397. 整数替换
// Created by Loading on 2021/11/19.
//

#include <bits/stdc++.h>

using namespace std;

int integerReplacement(int n) {
    if (n == 1) {
        return 0;
    }
    if (n % 2 == 0) {
        return 1 + integerReplacement(n / 2);
    } else {
        /* 此种写法当 n = INT_MAX 时，n + 1 会溢出，考虑到 + 1 后必然会 / 2，所以采用下面的写法 */
        // return 1 + min(integerReplacement(n + 1), integerReplacement(n - 1));
        return 1 + min(integerReplacement(n / 2 + 1) + 1, integerReplacement(n - 1));
    }
}

int main() {
    int n = 2104321259;
    int res = integerReplacement(n);
    cout << res << endl;

    return 0;
}